package com.itheima.demo5;

/*
程序的时间复杂度是o(log2n):所以不能从前往后这样取查找，要用二分查找
 */
public class Test {
    public static void main(String[] args) {
        // 目标：二分查找算法的应用。
        //先找到数组中间元素是否是target，然后分成左右两边，左右两边都用二分查找
        int[] nums = {5, 7, 7, 7, 7, 8, 8, 9};
        int leftIndex = getLeftIndex(nums, 7);
        int rightIndex = getRightIndex(nums, 7);
        System.out.println(leftIndex);
        System.out.println(rightIndex);
    }

    public static int getRightIndex(int[] nums, int target) {
        // 二分查找该数据的位置。
        int start = 0;
        int end = nums.length - 1;
        int rs = -1; // 假设这个数据不存在
        while (start <= end) {
            int middle = (start + end) / 2;
            if(target > nums[middle]) {
                start = middle + 1;
            }else if(target < nums[middle]) {
                end = middle - 1;
            }else {
                // 在数组的middle位置找到target数据，保存middle位置
                rs = middle;
                //此时分成两半，起始位置改为middle+1, 继续二分往右边再找找看
                //middle+1到nums.length-1这段元素又开始进行二分查找
                start = middle + 1;
            }
        }
        return rs;
    }

    public static int getLeftIndex(int[] nums, int target) {
        // 二分查找该数据的位置。
        int start = 0;
        int end = nums.length - 1;
        int rs = -1; // 假设这个数据不存在
        while (start <= end) {
            int middle = (start + end) / 2;
            if(target > nums[middle]) {
                //往右边找
                start = middle + 1;
            }else if(target < nums[middle]) {
                //往左边找
                end = middle - 1;
            }else {
                // 找到这个数据出现在middle索引处，记录middle索引
                rs = middle;
                // 继续二分往左边再找找看
                end = middle - 1;
            }
        }
        return rs;
    }

}
